package ahaArithmetic;

//Bellman_Ford算法 解决负权边
public class Bellman_Ford {
    //u到v
    static int[] u = new int[]{2,1,1,4,3};
    static int[] v = new int[]{3,2,5,5,4};
    static int[] w = new int[]{2,-3,5,2,3};
    static int n = 5;  //表示有5个节点
    static int m = 5; //表示有5条边
    static int a = 0;
    //单源最短路径 数组
    static int dis[] = new int[5];
    //0,1 分别代表 节点和路径

    public static void main(String[] args) {
        //初始化dis
        for(int i=0;i<m;i++){
            dis[i] = 88;
        }
        dis[0] = 0;

        for(int j=0;j<n;j++){
            a = 0;
            for(int k=0;k<m;k++ ){
                if(dis[v[k]-1] > dis[u[k]-1] + w[k]){
                    dis[v[k]-1] = dis[u[k]-1] + w[k];
                    a++;
                }
            }
            if(a == 0){
                break;
            }
        }

        for(int k:dis){
            System.out.print(k+" ");
        }
    }
}
